/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author zhongfang
 *
 */
public class MaximumLengthofPairChain {

	class Com implements Comparator<int[]> {

		@Override
		public int compare(int[] o1, int[] o2) {
			if (o1[0] != o2[0]) {
				return o1[0] - o2[0];
			}
			return (o1[1] - o1[0]) - (o2[1] - o2[0]);
		}
	}

	public int findLongestChain(int[][] pairs) {
		Com com = new Com();
		Arrays.sort(pairs, com);
		// for (int[] is : pairs) {
		// System.out.println(is[0] + " " + is[1]);
		// }
		int minEnd = pairs[0][1];
		int minEIndex = 0;
		for (int i = 1; i < pairs.length; i++) {
			if (minEnd > pairs[i][1]) {
				minEnd = pairs[i][1];
				minEIndex = i;
			}
		}
		int n = pairs.length;
		int curStart = pairs[0][1] + 1;
		int curTarget[] = { curStart, curStart };
		int count = 1;
		while (true) {
			int index = Arrays.binarySearch(pairs, curTarget, com);
			if (index < 0) {
				index = -index - 1;
			}
			if (index == n) {
				break;
			}
			count++;
			curStart = pairs[index][1] + 1;
			curTarget[0] = curTarget[1] = curStart;
		}
		return count;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] pairs = { { -6, 9 }, { 1, 6 }, { 8, 10 }, { -1, 4 }, { -6, -2 }, { -9, 8 }, { -5, 3 }, { 0, 3 } };
		System.out.println(new MaximumLengthofPairChain().findLongestChain(pairs));
	}

}
